package com.offer;

public class Test12 {

//    ["a","b","c","e"],
//    ["s","f","c","s"],
//    ["a","d","e","e"]]

    public boolean exist(char[][] board, String word) {
        if (board == null || board.length == 0 || board[0].length == 0) {
            return false;
        }

        char[] chars = word.toCharArray();

        boolean[][] visited = new boolean[board.length][board[0].length];
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (dfs(board, chars, visited, i, j, 0)) {
                    return true;
                }
            }
        }
        return false;
    }

    private boolean dfs(char[][] board, char[] chars, boolean[][] visited, int i, int j, int start) {
        if (i < 0 || i >= board.length || j < 0 || j >= board[0].length || chars[start] != board[i][j] || visited[i][j]) {
            return false;
        }

        if (start == chars.length - 1) {
            return true;
        }

        boolean result = false;
        visited[i][j] = true;

        result = dfs(board, chars, visited, i + 1, j, start + 1)
                || dfs(board, chars, visited, i - 1, j, start + 1)
                || dfs(board, chars, visited, i, j + 1, start + 1)
                || dfs(board, chars, visited, i, j - 1, start + 1);

        visited[i][j] = false;

        return result;
    }

    public static void main(String[] args) {
        Test12 test12 = new Test12();
        char[][] board = new char[3][4];
        board[0] = new char[]{'a', 'b', 'c', 'e'};
        board[1] = new char[]{'s', 'f', 'c', 's'};
        board[2] = new char[]{'a', 'd', 'e', 'e'};
        boolean result = test12.exist(board, "asfced");
        System.out.println(result);
    }

}
